// https://www.lintcode.com/problem/min-stack/description?_from=ladder&&fromId=6

// class MinStack {
// public:
//     priority_queue<int, vector<int>, greater<int>> q;
//     MinStack() {
//         // do intialization if necessary
//     }

//     /*
//      * @param number: An integer
//      * @return: nothing
//      */
//     void push(int number) {
//         q.push(number);
//     }

//     /*
//      * @return: An integer
//      */
//     int pop() {
//         int tmp = q.top();
//         q.pop();
//         return tmp;
//     }

//     /*
//      * @return: An integer
//      */
//     int min() {
//         return q.top();
//     }
// };


// pop的时候不是返回最小的，不能用优先队列/堆来做
class MinStack {
public:
    stack<int> s;
    stack<int> min_stack;
    MinStack() {
        // do intialization if necessary
    }

    /*
     * @param number: An integer
     * @return: nothing
     */
    void push(int number) {
        s.push(number);
        if (min_stack.empty()) //注意判断
        {
            min_stack.push(number);
            return;
        }
        int min_val = min_stack.top();
        if (number < min_val) min_stack.push(number);
        else min_stack.push(min_val);
    }

    /*
     * @return: An integer
     */
    int pop() {
        int tmp = s.top();
        s.pop();
        min_stack.pop();
        return tmp;
    }

    /*
     * @return: An integer
     */
    int min() {
        return min_stack.top();
    }
};